# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# class Solution:
#     def deleteDuplication(self, pHead):
#         # write code here
#         nodes = []
#         nodes_val = []
#         has_del = []
#         node = pHead
#         while node:
#             if  node.val not in has_del:
#                 if node.val not in nodes_val:
#                     nodes.append(node)
#                     nodes_val.append(node.val)
#                 else:
#                     node_index = nodes_val.index(node.val)
#                     nodes.pop(node_index)
#                     nodes_val.pop(node_index)
#                     has_del.append(node.val)
#             node = node.next
#         print(nodes_val)
#         if nodes:
#             for i in range(len(nodes)-1):
#                 nodes[i].next = nodes[i+1]
#             nodes[-1].next = None
#             return nodes[0]
#         else:
#             return None


# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        '''
        递归方法
        :param pHead:
        :return:
        '''
        # print(pHead.val)
        if not pHead or not pHead.next:
            return pHead
        if pHead.val == pHead.next.val:
            tmp = pHead.next
            while tmp and tmp.val == pHead.val:
                tmp = tmp.next
            return self.deleteDuplication(tmp)
        else:
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead





# 非递归方法
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead

        new_head = ListNode(-1)
        new_head.next = pHead
        pre_head = new_head
        ini_pre_head = pre_head
        last_head = pHead
        same_val = -1
        while last_head and last_head.next:
            if last_head.val == same_val:
                last_head = last_head.next
            elif last_head.val == last_head.next.val:
                same_val = last_head.val
                last_head = last_head.next.next
            else:
                pre_head.next = last_head
                pre_head = pre_head.next
                last_head = last_head.next
        if not last_head or last_head.val != same_val:
            pre_head.next = last_head
        else:
            pre_head.next = None
        return ini_pre_head.next